package algorithms.leaning.class32;

/**
 * indexTree单点更新，而线段树是范围更新
 * 前提：位置从1开始计算，原数组array，设计后的help数组
 * <p>
 * 结论1：给定help[i]，求包含的array数组的所有位置。i转成二进制减去最右侧1再加1，到i的范围就是包含的所有位置，左闭右闭
 * 例子：16 -> 10000，起始值 00001 终止值 10000，范围就是1到16之间的所有数
 * <p>
 * 结论2：求array中1到i的累加和，等于help数组中i位置的值加上i将最后1变0的位置的值，一直到0
 * 例子：求1-54的累加和，help[54] + help[52] + help[48] + help[32]
 * <p>
 * 结论3：更新array[i]的值时help数组中受影响的所有位置。help从i开始不断加最右侧的1
 *
 * @author guichang
 * @date 2021/7/4
 */

public class Code1_IndexTree_树状数组 {
}